1. Field Of the Invention
The invention relates generally to data storage and retrieval procedures in microprocessor-based systems, and more particularly, to improvements in cache memory management which is commonly utilized in such systems.
2. Description of Related Art
Cache memories are high-speed memories that are positioned between microprocessors and main memories in a computer system in order to improve system performance. Cache memories (or caches) store copies of portions of main memory that are actively being used by the central processing unit (CPU) while a program is running. Since the access time of a cache can be faster than that of main memory, the overall access time can be reduced.
Use of small, high speed caches in computer designs permits the use of relatively slow but inexpensive Dynamic Random Access Memories (DRAMs) for the large main memory space, by taking advantage of the "property of temporal locality," i.e., the property inherent in most computer programs wherein a memory location referenced at one point in time is very likely to be referenced again soon thereafter. Descriptions of the various uses of and methods of employing caches appear in the following articles: Kaplan, "Cache-based Computer Systems," Computer, 3/73 at 30-36; Rhodes, "Caches Keep Main Memories From Slowing Down Fast CPUs," Electronic Design, Jan. 21, 1982, at 179; Strecker, "Cache-Memories for PDP-11 Family Computers," in Bell, "Computer Engineering" (Digital Press), at 263-67, all incorporated herein by reference. See also the description at pp. 6-1 through 6-11 of the "i486 Processor Hardware Reference Manual" mentioned above.
Many microprocessor-based systems implement a "direct mapped" cache memory to improve performance. In general, a direct mapped cache memory comprises a high speed data Random Access Memory (RAM) and a parallel high speed tag RAM. The RAM address of each line in the data cache is the same as the low-order portion of the main memory line address to which the entry corresponds, the high-order portion of the main memory address being stored in the tag RAM. Thus, if main memory is thought of as 2.sup.m blocks of 2.sup.n "lines" of one or more bytes each, the i'th line in the cache data RAM will be a copy of the i'th line of one of the 2.sup.m blocks in main memory. The identity of the main memory block that the line came from is stored in the i'th location in the tag RAM. Tag RAM also typically contains a "valid" bit corresponding to each entry, indicating whether the tag and data in that entry are valid.
When a CPU requests data from memory, the low-order portion of the line address is supplied as an address to both the cache data and cache tag RAMs. The tag for the selected cache entry is compared with the high-order portion of the CPU's address and, if it matches, then a "cache hit" is indicated and the data from the cache data RAM is enabled onto a data bus of the system. If the tag does not match the high-order portion of the CPU's address, or the tag data is invalid, then a "cache miss" is indicated and the data is fetched from main memory. It is also placed in the cache for potential future use, overwriting the previous entry. Typically, an entire line is read from main memory and placed in the cache on a cache miss, even if only a byte is requested. On a data write from the CPU, either the cache RAM or main memory or both may be updated, it being understood that flags may be necessary to indicate to one that a write has occurred in the other.
Accordingly, in a direct mapped cache, each "line" of secondary memory can be mapped to one and only one line in the cache. In a "fully associative" cache, a particular line of secondary memory may be mapped to any of the lines in the cache; in this case, in a cacheable access, all of the tags must be compared to the address in order to determine whether a cache hit or miss has occurred. "k-way set associative" cache architectures also exist which represent a compromise between direct mapped caches and fully associative caches. In a k-way set associative cache architecture, each line of secondary memory may be mapped to any of k lines in the cache. In this case, k tags must be compared to the address during a cacheable secondary memory access in order to determine whether a cache hit or miss has occurred. Caches may also be "sector buffered" or "sub-block" type caches, in which several cache data lines, each with its own valid bit, correspond to a single cache tag RAM entry.
When the CPU executes instructions that modify the contents of the cache, these modifications must also be made in the main memory or the data in main memory will become "stale." There are two conventional techniques for keeping the contents of the main memory consistent with that of the cache--(1) the write-through method and (2) the write-back or copy-back method.
In the write-through method, on a cache write hit, data is written to the main memory immediately after or while data is written into the cache. This enables the contents of the main memory always to be valid and consistent with that of the cache. An advantage of the write-through method is that any line of data in the cache can later be overwritten, for example, on a read from another location in main memory that maps to the same line of cache, without data loss. The write-through method has a disadvantage of increasing secondary memory write traffic on the CPU bus because every write cycle requires the use of secondary memory.
In the write-back method, on a cache write hit, the system writes data into the cache and sets a "dirty bit" which indicates that a data word has been written into the cache but not into the main memory. A cache controller checks for a dirty bit before overwriting any line of data in the cache, and if set, writes the line of data out to main memory before loading the cache with new data.
An advantage of the write-back method is a decreased amount of main memory accesses as compared with the write-through method. The write-back method accesses the main memory less often than the write-through method because the number of times that the main memory must be updated with altered cache information is usually lower than the number of write accesses. This, of course, reduces the amount of traffic on the main memory data bus, which can result in higher performance than a write-through cache if writes to the main memory are comparatively slow.
Accordingly, it would be desirable to provide a cache-based system that utilizes advantageous features of both the write-through and write-back methods, while also avoiding disadvantages of either method.